﻿#pragma once

#include <functional>
#include <iostream>
#include <memory>
#include <unordered_set>

#include <learn/check.h>

namespace xi
{

namespace stl
{

namespace details
{

template <class T> struct List_Node
{
    T data{};
    std::shared_ptr<List_Node<T>> next{nullptr};
};

} // namespace details

template <class T> class List
{
    template <class U> using List_Node = details::List_Node<U>;

  protected:
    std::size_t m_size = 0;
    std::shared_ptr<List_Node<T>> m_head = nullptr;

  public:
    List(List &&) = delete;

    /**
     * @brief 默认构造函数
     *
     */
    List() = default;

    /**
     * @brief 判断是否为空
     *
     * @return true
     * @return false
     */
    constexpr bool empty() const noexcept
    {
        return m_head == nullptr;
    }

    /**
     * @brief 获得元素数量
     *
     * @return constexpr std::size_t
     */
    constexpr std::size_t size() const noexcept
    {
        return m_size;
    }

    /**
     * @brief 从头部插入元素
     *
     * @param[in] data
     */
    void push_front(const T &data)
    {
        auto node = std::make_shared<List_Node<T>>(data, m_head);
        m_head = node;
        m_size++;
    }

    /**
     * @brief 从头部弹出元素
     *
     * @return T
     */
    T pop_front()
    {
        auto pop = m_head;
        m_head = m_head->next;
        m_size--;
        return pop->data;
    }

    /**
     * @brief 获得头部元素
     *
     * @return T&
     */
    T &front()
    {
        ASSERT_INFO(!empty(), "List is empty");
        return m_head->data;
    }

    /**
     * @brief 获得头部元素
     *
     * @return const T&
     */
    const T &front() const
    {
        ASSERT_INFO(!empty(), "List is empty");
        return m_head->data;
    }

    /**
     * @brief 删除第一个匹配元素，返回是否成功
     *
     * @param[in] data
     * @return true
     * @return false
     */
    bool remove(const T &data)
    {
        if (empty())
            return false;

        if (m_head->data == data)
        {
            m_head = m_head->next;
            m_size--;
            return true;
        }

        auto prev = m_head;
        auto curr = m_head->next;
        while (curr)
        {
            if (curr->data == data)
            {
                prev->next = curr->next;
                m_size--;
                return true;
            }
            prev = curr;
            curr = curr->next;
        }
        return false;
    }

    /**
     * @brief 删除所有匹配元素，返回删除的数量
     *
     * @param[in] pred
     * @return std::size_t
     */
    std::size_t remove_if(std::function<bool(const T &)> &&pred)
    {
        if (empty())
            return 0;

        if (pred(m_head->data))
        {
            m_head = m_head->next;
            m_size--;
            return 1;
        }

        std::size_t count = 0;
        auto prev = m_head;
        auto curr = m_head->next;
        while (curr)
        {
            if (pred(curr->data))
            {
                prev->next = curr->next;
                ++count;
                m_size--;
            }
            prev = curr;
            curr = curr->next;
        }
        return count;
    }

    /**
     * @brief 移除重复元素
     *
     * @return std::size_t
     */
    std::size_t remove_duplicates()
    {
        if (empty())
            return 0;

        std::size_t count = size();
        std::unordered_set<T> set;
        while (!empty())
            set.insert(pop_front());

        for (auto &data : set)
            push_front(data);

        return count - size();
    }

    struct Iterator
    {
        using value_type = T;
        using reference = T &;
        using pointer = T *;
        using difference_type = std::ptrdiff_t;
        using iterator_category = std::forward_iterator_tag;

        /**
         * @brief 默认构造
         *
         * @param[in] node
         */
        Iterator(std::shared_ptr<List_Node<T>> node) : m_node(node)
        {
        }

        /**
         * @brief 取值
         *
         * @return reference
         */
        reference operator*() const
        {
            return m_node->data;
        }

        /**
         * @brief 取指针
         *
         * @return pointer
         */
        pointer operator->() const
        {
            return &m_node->data;
        }

        /**
         * @brief 迭代器递增
         *
         * @param[in] n
         * @return Iterator&
         */
        Iterator &operator+(std::size_t n)
        {
            for (std::size_t i = 0; i < n; ++i)
                m_node = m_node->next;
            return *this;
        }

        /**
         * @brief 前置递增
         *
         * @return Iterator&
         */
        Iterator &operator++()
        {
            m_node = m_node->next;
            return *this;
        }

        /**
         * @brief 后置递增
         *
         * @return Iterator
         */
        Iterator operator++(int)
        {
            Iterator tmp = *this;
            ++(*this);
            return tmp;
        }

        /**
         * @brief 判断相等
         *
         * @param[in] other
         * @return true
         * @return false
         */
        bool operator==(const Iterator &other) const
        {
            return m_node == other.m_node;
        }

        /**
         * @brief 判断不等
         *
         * @param[in] other
         * @return true
         * @return false
         */
        bool operator!=(const Iterator &other) const
        {
            return m_node != other.m_node;
        }

      private:
        std::shared_ptr<List_Node<T>> m_node;
    };

    /**
     * @brief 初始迭代器
     *
     * @return Iterator
     */
    Iterator begin() const
    {
        return Iterator(m_head);
    }

    /**
     * @brief 尾后迭代器
     *
     * @return Iterator
     */
    Iterator end() const
    {
        // 注意这里返回空指针，不是实际上的尾后迭代器
        return Iterator(nullptr);
    }

    /**
     * @brief 检查是否存在元素
     *
     * @param[in] data
     * @return Iterator
     */
    Iterator find(const T &data) const
    {
        if (empty())
            return end();

        for (auto it = begin(); it != end(); ++it)
        {
            if (*it == data)
                return it;
        }
        return end();
    }

    /**
     * @brief 返回第一个匹配元素的迭代器
     *
     * @param[in] pred
     * @return Iterator
     */
    Iterator find_if(std::function<bool(const T &)> &&pred) const
    {
        if (empty())
            return end();

        for (auto it = begin(); it != end(); ++it)
        {
            if (pred(*it))
                return it;
        }
        return end();
    }

    /**
     * @brief 遍历输出
     *
     * @param[in] os
     * @param[in] list
     * @return std::ostream&
     */
    friend std::ostream &operator<<(std::ostream &os, const List &list)
    {
        for (auto it = list.begin(); it != list.end(); ++it)
            os << *it << " ";
        return os;
    }
};

} // namespace stl

} // namespace xi
